package class09_01_bucketSort;
//基数排序
public class BucketSort {
    public static void bucketSort(int[] arr){
        int max = 0;
        for (int i = 0; i < arr.length; i++) {  //找到最大数
            if(arr[i]>max) max = arr[i];
        }

        int digit=0;
        while(max>0){   //找到最大数的位数
            max/=10;
            digit++;
        }

        int[] thisDigitCounter = new int[10];

        for(int i = 0; i<digit; i++){
            int div = 1; for(int j = 0;j<i;j++) div*=10;//等等用于获取特定位的数字 (arr[j]/div)%10

            int[] res = new int[arr.length];
            for(int j=0; j< 10; j++){
                thisDigitCounter[j]=0;//计数器清零
            }
            for(int j=0; j< arr.length; j++){
                thisDigitCounter[(arr[j]/div)%10]++;//统计为该位有多少数
            }
            for(int j=1; j< 10; j++){
                //得到累加和，也即该数位各个可能的数最大可以排的位置
                thisDigitCounter[j]=thisDigitCounter[j]+thisDigitCounter[j-1];
            }

            for (int j = arr.length-1 ; j >= 0 ; j--) {
                //从后往前，查找该数位对应的最后位置，放入后最后位置提前
                //因为是累加，而下标从0 开始，所以下标比累加小1所以先--
                res[--thisDigitCounter[(arr[j]/div)%10]]=arr[j];
            }

            for (int j = 0; j<arr.length; j++){
                arr[j] = res[j];
            }
        }
    }

    public static int[] randomArr (int maxLen,int maxValue)
    {
        int len = (int)(maxLen*Math.random());
        int[] arr =new int[len];

        for(int i = 0; i<len; i++)
        {
            arr[i] = (int)(maxValue*Math.random());
        }
        return arr;
    }

    public static boolean isOrder(int[] arr)
    {
        int len = arr.length;

        for(int i = 0; i<len-1; i++)
        {
            if(arr[i+1]<arr[i])
            {
                return false;
            }
        }
        return true;
    }

    public static void swap(int[] arr, int index1, int index2)
    {

//        arr[index1] = arr[index1]^arr[index2];
//        arr[index2] = arr[index1]^arr[index2];
//        arr[index1] = arr[index1]^arr[index2];
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void main(String[] args) {
        int[] arr = randomArr(1000,10000);
        bucketSort(arr);
        for (int num: arr) {
            System.out.print(num+" ");
        }
        System.out.println(isOrder(arr));
    }
}
